package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.List;

import zcw.com.lib_leet_code.bean.ListNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/12.<br><br>
 *
 * 回文链表
 */
public class Topic234 {
    public static void main(String[] args) {
        Topic234 instance = new Topic234();

        int[] array = new int[] {1,2,2,1};
        ListNode head = Util.createList(array);
        System.out.println(instance.isPalindrome(head));

        array = new int[] {1,2};
        head = Util.createList(array);
        System.out.println(instance.isPalindrome(head));
    }

    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }

        ListNode fast = head;
        ListNode newHead = null;
        ListNode temp;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;

            temp = head;
            head = head.next;

            temp.next = newHead;
            newHead = temp;
        }

        if(fast != null) {
            head = head.next;
        }

        while (head != null && newHead != null) {
            if(head.val != newHead.val) {
                return false;
            }

            head = head.next;
            newHead = newHead.next;
        }

        return true;
    }

    public boolean isPalindrome2(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }

        List<Integer> start = new ArrayList<>();
        List<Integer> end = new ArrayList<>();

        while (head != null) {
            start.add(0, head.val);
            end.add(head.val);

            head = head.next;
        }

        for(int i = 0; i < start.size(); i++) {
            if(!start.get(i).equals(end.get(i))) {
                return false;
            }
        }

        return true;
    }
}
